package com.LeeCode;

/**
 * 二叉树中的链表
 */

public class Code1367 {
    public static void main(String[] args) {
        Integer[] arr = {1, null, 1, 10, 1, 9};
        int[] nums = {1, 10};
        TreeNode root = Utils.buildTree(arr);
        ListNode head = Utils.arrayToListNode(nums);
        System.out.println(new Code1367().isSubPath(head, root));
    }

    private ListNode head;

    public boolean isSubPath(ListNode head, TreeNode root) {
        this.head = head;
        return dfs(head, root);
    }

    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) return true;

        if (root == null) return false;
        return root.val == head.val && (dfs(head.next, root.left) || dfs(head.next, root.right)) ||
                head == this.head && (dfs(this.head, root.left) || dfs(this.head, root.right));
    }
}
